import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;

class Solution6 {
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();

        //第一行
        List<Integer> FirstRow = new ArrayList<>();
        FirstRow.add(1);

        //放第一行
        list.add(FirstRow);


        for (int i = 1; i < numRows; i++) {
            //当前行
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);
            for (int j = 1; j < i; j++) {
                curRow.add(list.get(i - 1).get(j) + list.get(i - 1).get(j - 1));
            }
            curRow.add(i,1);
            list.add(curRow);
        }
        return list;
    }
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int pot1 = m - 1,pot2 = n - 1,set = nums1.length - 1;
        while(pot1 >= 0 && pot2 >= 0) {
            if(nums1[pot1] > nums2[pot2]) {
                nums1[set] = nums1[pot1];
                pot1--;
                set--;
            }else {
                nums1[set] = nums2[pot2];
                pot2--;
                set--;
            }
        }
        if(pot1 < 0) {
            for(int i = 0;i <= pot2;i++) {
                nums1[i] = nums2[i];
            }
        }
    }
    public static int removeDuplicates(int[] nums) {
        int effecount = nums.length;
        for (int i = 0; i < effecount; i++) {
            if(nums[i] == nums[i + 1]) {
                for (int j = i; j < effecount - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                effecount--;
                i--;
            }
        }
        return effecount;
    }
    public static int removeElement(int[] nums, int val) {
        int effecount = nums.length;
        for (int i = 0; i < effecount; i++) {
            if(nums[i] == val) {
                for (int j = i; j < effecount - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                i--;
                effecount--;
            }
        }
        return effecount;
    }

    public static void main(String[] args) {
        /*int[] nums = {0,1,2,2,3,0,4,2};
        int val = 2;
        int ret = removeElement(nums,val);
        System.out.println(Arrays.toString(nums));
        System.out.println(ret);*/

        /*int[] nums = {0,1,2,2,3,0,4,2};
        int val = 2;
        int ret = removeElement(nums,val);
        System.out.println(Arrays.toString(nums));
        System.out.println(ret);*/

        /*int[] nums1 = {4,5,6,0,0,0};
        int[] nums2 = {1,2,3};
        merge(nums1,3,nums2,3);
        System.out.println(Arrays.toString(nums1));*/

        generate(5);

    }
}